﻿//https://leetcode.cn/problems/integer-replacement/

//递归+记忆化搜索

class Solution {
    unordered_map<int, int> hash;
public:
    int integerReplacement(int n)
    {
        return dfs(n);
    }

    int dfs(long long n)
    {
        if (n == 1)
        {
            return 0;
        }

        if (hash.count(n))
        {
            return hash[n];
        }

        if (n % 2 == 0)
        {
            hash[n] = 1 + dfs(n / 2);
            return hash[n];
        }

        else
        {
            hash[n] = 1 + min(dfs(n - 1), dfs(n + 1));
            return hash[n];
        }
    }
};

//贪心
class Solution {
public:
    int integerReplacement(int n) {
        int ret = 0;
        while (n > 1)
        {
            // n为偶数
            if (n % 2 == 0)
            {
                n /= 2;
                ret++;
            }
            // n为奇数
            else
            {
                if (n == 3)
                {
                    ret += 2;
                    n = 1;
                }
                else if (n % 4 == 1)
                {
                    n /= 2;
                    ret += 2;
                }
                else if (n % 4 == 3)
                {
                    n = n / 2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
};
